/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._889;

import java.util.HashMap;
import java.util.Map;

/**
 * 返回与给定的前序和后序遍历匹配的任何二叉树。
 * <p>
 *  pre 和 post 遍历中的值是不同的正整数。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
 * 输出：[1,2,3,4,5,6,7]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= pre.length == post.length <= 30
 * pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
 * 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._889
 * @ClassName: ConstructBinaryTree
 * @Author: linyaonan
 * @Date: 2020/1/20 15:35
 */
public class ConstructBinaryTree {
    Map<Integer, Integer> map;

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        map = new HashMap<>();
        // 记录后序遍历的坐标位置
        for (int i = 0; i < post.length; i++) {
            map.put(post[i], i);
        }
        return build(pre, 0, pre.length - 1, post, 0, post.length - 1);
    }

    private TreeNode build(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd) {
        if (preStart > preEnd || postStart > postEnd) {
            return null;
        } else {
            int rootValue = pre[preStart];
            TreeNode root = new TreeNode(rootValue);
            if (preStart + 1 <= preEnd) {
                int leftValue = pre[preStart + 1];
                Integer postEndIndex = map.get(leftValue);
                int count = postEndIndex - postStart;
                root.left = build(pre, preStart + 1, preStart + 1 + count, post, postStart, postStart + count);
                root.right = build(pre, preStart + 2 + count, preEnd, post, postStart + count + 1, postEnd - 1);
            }
            return root;
        }
    }
}
